package l.l.w.leetcode.SearchForARange;

/**
 * Created by llw on 2017/11/5.
 */
public class SearchForARange {

    public int[] searchRange(int[] nums, int target) {
        int start = -1, end = -1;
        if(nums == null || nums.length == 0 || nums[0] >target || nums[nums.length-1] < target) return new int[]{start,end};
        int i = 0, j = nums.length-1, mid = (i+j)/2;
        boolean isFound = false;
        int lstart = -1,lend = -1,lmid = -1, rstart = -1, rend = -1, rmid = -1;
        while(i < j){
            if(nums[mid] > target){
                j = mid-1;
                mid = (i+j)/2;
            }else if(nums[mid] < target){
                i = mid+1;
                mid = (i+j)/2;
            }else{
                lstart = i;lend = mid;lmid = (lstart+lend)/2;
                while(lstart < lend){
                    if(nums[lmid] == target){
                        lend = lmid-1;
                        lmid = (lstart+lend)/2;
                    }else {
                        lstart = lmid+1;
                        lmid = (lstart+lend)/2;
                    }
                }
                if(nums[lstart]!= target) lstart = lstart +1;
                rstart = mid;rend = j;rmid = (rstart+rend)/2;
                while(rstart <rend){
                    if(nums[rmid] == target){
                        rstart = rmid+1;
                        rmid = (rstart+rend)/2;
                    }else{
                        rend = rmid-1;
                        rmid = (rstart+rend)/2;
                    }
                }
                if(nums[rend] != target) rend = rend-1;
                start = lstart;
                end = rend;
                break;
            }
        }
        return  new int[]{start,end};
    }

    public static void main(String[] args) {
        int[] a = {1,5};
        int target = 4;
        int[] result = new SearchForARange().searchRange(a, target);
        System.out.println(result[0]+" "+result[1]);
    }
}
